/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.graph.dfs;

/**
 * <p>
 * 岛的个数，1为岛，0为水
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月25日
 */
public class NumberOfIslands {

    public int numIslands(char[][] grid) {
        if(grid==null ){
            return 0;
        }
        int m = grid.length;
        if(m==0){
            return 0;
        }
        int n = grid[0].length;
        if(n==0){
            return 0;
        }
        int [][]visited = new int[m][n];
        int count = 0;
        for(int i = 0;i<m;i++){
            for(int j=0;j<n;j++){
                //找出一个未访问的元素
                if(visited[i][j]==0 && grid[i][j] =='1'){
                    dfs(grid,i,j,visited);
                    count++;
                }
                
            }
        }
        return count;
        }

        /**
         * @param grid
         * @param x
         * @param y
         * @param visited
         * @author towan 2015年5月28日
         */
        private void dfs(char[][] grid, int x, int y, int[][] visited) {
            if(visited[x][y]!=0){
                return ;
            }
            visited[x][y] =1;
            //left
            if(x>0 && visited[x-1][y]==0 && grid[x-1][y]=='1'){
                dfs(grid, x-1, y, visited);
            }
            //down
            if(y>0 && visited[x][y-1]==0 && grid[x][y-1]=='1'){
                dfs(grid, x, y-1, visited);
            }
            //right
            if(x<grid.length-1 && visited[x+1][y]==0 && grid[x+1][y]=='1'){
                dfs(grid, x+1, y, visited);
            }
            //up
            if(y<grid[0].length-1 && visited[x][y+1]==0 && grid[x][y+1]=='1'){
                dfs(grid, x, y+1, visited);
            }
        }
}
